Search for: All records

We revisit the fundamental question of simple-versus-simple hypothesis testing with an eye toward computational complexity, as the statistically optimal likelihood ratio test is often computationally intractable in high-dimensional settings. In the classical spiked Wigner model with a general i.i.d. spike prior, we show (conditional on a conjecture) that an existing test based on linear spectral statistics achieves the best possible trade-off curve between type-I and type-II error rates among all computationally efficient tests, even though there are exponential-time tests that do better. This result is conditional on an appropriate complexity-theoretic conjecture, namely a natural strengthening of the well-established low-degree conjecture. Our result shows that the spectrum is a sufficient statistic for computationally bounded tests (but not for all tests). To our knowledge, our approach gives the first tool for reasoning about the precise asymptotic testing error achievable with efficient computation. The main ingredients required for our hardness result are a sharp bound on the norm of the low-degree likelihood ratio along with (counterintuitively) a positive result on achievability of testing. This strategy appears to be new even in the setting of unbounded computation, in which case it gives an alternate way to analyze the fundamental statistical limits of testing. 

ABSTRACT Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem that has been extensively studied in recent years. We study a hypergraph version of the problem. Let denote the ‐uniform Erdős–Rényi hypergraph model with vertices and edge density . We consider detecting the presence of a planted subhypergraph in a hypergraph, where and . Focusing on tests that are degree‐ polynomials of the entries of the adjacency tensor, we determine the threshold between the easy and hard regimes for the detection problem. More precisely, for , the threshold is given by , and for , the threshold is given by . Our results are already new in the graph case , as we consider the subtlelog‐density regimewhere hardness based on average‐case reductions is not known. Our proof of low‐degree hardness is based on aconditionalvariant of the standard low‐degree likelihood calculation.